package cc.wsyw126.java.lintCode;///**
// * Definition for Directed graph.
// * class DirectedGraphNode {
// *     int label;
// *     ArrayList<DirectedGraphNode> neighbors;
// *     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
// * };
// */
//public class Solution {
//    /**
//     * @param nodes a array of Directed graph node
//     * @return a connected set of a directed graph
//     */
//     
//    class UnionFind{
//        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
//        UnionFind(HashSet<Integer> hashset){
//            for(Integer node:hashset)
//                map.put(node,node);
//        }
//        
//        int find(int x){
//            int temp=x;
//            while(temp!=map.get(temp)){
//                temp=map.get(temp);
//            }
//            return temp;
//        }
//        
//        int uionfind(int x){
//            int temp=x;
//            while(temp!=map.get(temp)){
//                temp=map.get(temp);
//            }
//            int temp2=x;
//            int fa=map.get(x);
//            while(temp2!=map.get(temp2)){
//                map.put(temp2,temp);
//                temp2=fa;
//                fa=map.get(fa);
//            }
//            return temp;
//        }
//        void jion(int x,int y){
//            int fx=find(x);
//            int fy=find(y);
//            if(fx!=fy)
//                map.put(fx,fy);
//        }
//    }
//    
//    
//    public List<List<Integer>> print(HashSet<Integer> hashset,UnionFind uf,int size){
//        List<List <Integer> > ans = new ArrayList<List<Integer>>();
//        HashMap<Integer, List <Integer>> hashmap = new HashMap<Integer, List <Integer>>();
//        for(int i:hashset){
//            int fa = uf.find(i);
//            if(!hashmap.containsKey(fa)){
//                hashmap.put(fa,  new ArrayList<Integer>() );
//            }
//            List <Integer> now =  hashmap.get(fa);
//            now.add(i);
//            hashmap.put(fa,now);
//        }
//        
//        for(List<Integer> list:hashmap.values()){
//            Collections.sort(list);
//            ans.add(list);
//        }
//        return ans;
//    }
//    
//    public List<List<Integer>> connectedSet2(ArrayList<DirectedGraphNode> nodes) {
//        HashSet<Integer> hashset=new HashSet<Integer>(); 
//        for(DirectedGraphNode node:nodes){
//            hashset.add(node.label);
//            for(DirectedGraphNode neighbor:node.neighbors){
//                hashset.add(neighbor.label);
//            }
//        }
//        UnionFind uf=new UnionFind(hashset);
//        for(DirectedGraphNode node:nodes){
//            int fnode=uf.find(node.label);
//            for(DirectedGraphNode neighbor:node.neighbors){
//                int fneighbor=uf.find(neighbor.label);
//                if(fnode!=fneighbor){
//                    uf.jion(node.label, neighbor.label);
//                }
//            }
//        }
//        return print(hashset,uf,nodes.size());
//    }
//}
